class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true; // 空链表或只有一个节点的链表是回文
        }

        // 1找到链表的中间节点
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: 反转链表的后半部分
        ListNode prev = null;
        ListNode curr = slow;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // 3比较前后两部分是否相等
        ListNode left = head;
        ListNode right = prev; // 反转后的后半部分的头节点
        boolean isPalindrome = true;
        while (right != null) { // 右半部分长度小于等于左半部分
            if (left.val != right.val) {
                isPalindrome = false;
                break;
            }
            left = left.next;
            right = right.next;
        }

        // 恢复链表（可选）
        // 如果需要保持链表的原始结构，可以再次反转后半部分
        // 反转链表的后半部分
        ListNode prev2 = null;
        ListNode curr2 = prev; // 从反转后的头节点开始
        while (curr2 != null) {
            ListNode nextTemp2 = curr2.next;
            curr2.next = prev2;
            prev2 = curr2;
            curr2 = nextTemp2;
        }

        return isPalindrome;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // 测试样例：1->2->2->1
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(1);

        System.out.println(solution.isPalindrome(head)); // 输出：true
    }
}